|
A kinetic Euclidean minimum spanning tree is a kinetic data structure that maintains the Euclidean minimum spanning tree (EMST) of a set ''P'' of ''n'' points that are moving continuously. For the set of points ''P'' in 2-dimensional space, there are two kinetic algorithms for maintenance of the EMST. Rahmati and Zarei〔 build a kinetic data structure based on the kinetic Delaunay triangulation to handle updates to the EMST in polylog time per event. Their kinetic data structure handles events, where m is the number of all changes to the Delaunay triangulation of the moving points. Their kinetic approach can work well for maintenance of the minimum spanning tree (MST) of a planar graph whose edge weights are changing as a continuous function of time. Abam, Rahmati, and Zarei〔 provide a significant improvement on exact kinetic maintenance on the Euclidean minimum spanning tree. Their kinetic data structure handles a nearly cubic number of events. == References == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kinetic Euclidean minimum spanning tree」の詳細全文を読む スポンサード リンク
|